136. Single Number

今天要挑戰把一個陣列中，沒有與自己相同的數字找出來，讓我們一起來試看看吧！

題目

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,1]
Output: 1
Example 2:

Input: nums = [4,1,2,1,2]
Output: 4
Example 3:

Input: nums = [1]
Output: 1

這題的意思比較簡單明暸，就是題目會給我們一個陣列，之中存的是整數，並且恰好會只有一個數是自己單獨出現，其他都會成對出現的，我們必須找到那個數，而且是在big O(n)的時間複雜度內

HashMap

這題同樣可以通過HashMap來達到，我們只要對題目給我們的List跑一次迴圈，確認走訪到的元素是否在HashMap之中，如果不在我們便將其放進去，如果在的話表示他已經出現過了，我們就把HashMap中的那個元素拿掉，迴圈跑完後，還待在HashMap中的Key就是我們要的答案了。
而因為HashMap的查找和刪除，時間複雜度都是Ｏ(1)，因此我們可以確保這符合題目要求的線性複雜度。

以下為python3的程式碼

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count_dic = {}  
        for i in nums:  #Ｏ(n)
            if i in count_dic: # Ｏ(1) (HsahMap)
                del count_dic[i] 
            else:
                count_dic[i] = 1
                
        return [key for key in count_dic][-1]

XOR

除了上述利用HashMap能達到Ｏ(n)的複雜度，還可以用更特別的方法。在電腦運算中，有一種邏輯運算是XOR，概念上就是exclusive的OR，比較貼近生活上我們講的或，只能有一個條件是True的時候才會輸出True。

當然在這題上我們只需要知道他的應用性在於，自己XOR自己一定是0，而0 XOR任何數都會是那個任何數，透過這樣的概念我們只要對陣列中每個元素逐一進行XOR運算，到最後的結果必定會是個數是一的數，最主要原因是其他重複出現的元素正好只會出現兩次。

在以下程式碼中，這個^符號代表XOR的運算。

以下是C++的程式碼

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size(); i++)
            res ^= nums[i];
        
        return res;
    }
};